In today's integrated communication networks, such as Asynchronous Transfer Mode (ATM) networks, which support a diversity of applications (e.g., data, voice, video, etc.), allocation of network resources is based on quality of service (QoS) requirements associated with the applications. Network demand is often divided into a number of service categories, such as constant bit rate (CBR) service, available bit rate (ABR) service, etc. One can consider network users to be divided into a plurality of priority classes, whereby different classes of users may require different levels of QoS. For example, some users may generate steady streams of messages while others may generate messages in a bursty manner.
A multiple access protocol is a mechanism that is used to allocate transmission resources (e.g., time slots and frequency bands) for user data transmission in a communication channel among a plurality of users. The terminology "user data" or simply "data" is used herein generically to refer to various kinds of user information including not only data, but also voice, video, etc. User data is distinguished from control information that the network generates to enable proper operation of network protocols.
A multiple access protocol may be contention-free or contention-based. A contention-free multiple access protocol apportions available transmission resources into non-overlapping segments and assigns one segment exclusively to each user. A contention-based multiple access protocol allows multiple users to simultaneously transmit messages to access the channel, and resolve collisions after they have occurred.
In contention-free multiple access protocols, the assignment of resource segments can be on a fixed basis or on a demand basis. In the fixed assignment approach, such as time-division multiple access (TDMA) and frequency-division multiple access (FDMA), resources allocated to a user are wasted when the user has nothing to transmit. Thus, these protocols are not efficient for networks that support a large population of users who are idle some of the time. In general, although fixed assignment multiple access schemes are very simple, they are not very efficient in networks supporting integrated services, especially when some services tend to generate messages in a bursty manner. Nonetheless, fixed assignment multiple access protocols generally perform well when the network is heavily loaded with a steady stream of user data from each user. In the demand assignment approach, a user either relinquishes its allocated resources when they are not needed (e.g., token passing), or reserves required resources when they are needed. A fraction of the channel is sometimes used for exchanging control information to support a reservation mechanism so that transmission of user data may be scheduled to avoid collisions. This reservation subchannel itself requires a multiple access protocol for coordinating transmission of reservation messages.
In contention-based multiple access protocols, there are two existing approaches to dealing with collisions. The terms "collision" and "contention" are used interchangeably herein. In one approach, each user that has been involved in a collision retransmits his message after some random amount of time. In another approach, a contention resolution algorithm is used to determine when the users who are involved in a collision may subsequently retransmit their messages, and meanwhile, all users that are not involved in the collision must wait until the collision is resolved. Contention-based multiple access protocols are known to have poor performance when the network is heavily loaded, as there can be many wasteful collisions. Nonetheless, when the network is lightly loaded, these protocols generally offer better performance than fixed assignment multiple access protocols. Since transmission resources are not divided among users a priori, these protocols are quite suitable for networks that support a large population of users, provided that only a small subset of the users are busy at any time.
Prior art has shown a combined random/reservation multiple access (CRRMA) scheme, in which transmission of reservation messages by a large population of bursty users utilizes a random access strategy. In this approach, a contention-based protocol is used for transmission of reservation messages in a reservation subchannel. Each data slot in a data subchannel is either reserved for a particular user or open for contention. The allocation of reserved data slots in the data subchannel is scheduled by a centralized scheduler.
In prior art for contention resolution, a splitting algorithm, known as the Binary Tree Splitting Algorithm (BTSA), is used to schedule retransmissions of messages after they have collided. The central idea of the original splitting algorithm is based on a concept of probabilistically splitting the set of users involved in a collision into a transmitting set and a nontransmitting set while making other users wait. Each of the two sets may contain zero, one, or more than one of the contending users. If by chance each of the two sets contains at most one user, then the contention is said to have been resolved. The user in the transmitting set, if any, would transmit first, and determine that he is successful. The user in the non-transmitting set, if any, would transmit next, and also determine that he is successful. If any of the two sets contains more than one user, then a collision will occur again. In this case, the set with contending users is subdivided into smaller transmitting and nontransmitting sets. In this respect, the splitting algorithm is recursive. The algorithm stops when each set contains at most one user. A splitting algorithm may be implemented with a stack.
The prior art includes Distributed Scheduling Multiple Access (DSMA) for scheduling multiple access transmissions. DSMA supports users belonging to different priority classes, but relies on distinct and serially transmitted user addresses to avoid collisions. DSMA also uses a data subchannel for transmission of data messages and a reservation subchannel for transmission of reservation messages. In this scheme, each user is assigned an n-bit address a priori (n being a predetermined integer). In the absence of priority scheduling, the system can accommodate up to 2.sup.n -1 users, numbered from 1 to (2.sup.n -1). Each user with data pending transmission transmits his unique address bits serially, with the most significant bit first, into the reservation subchannel. A reservation frame is completed when all users have received feedback regarding all the n reservation slots. The reservation subchannel is logically a simple OR circuit, such that the feedback in the reservation subchannel is binary (i.e., one may only distinguish between no transmission or at least one transmission of a bit of value 1 in each bit position of the serial address). A user with an address lower than that of another user in the same reservation frame temporarily discontinues further transmission in the reservation subchannel until a busy user with the higher address is identified. Each active user is guaranteed reservation for a data slot per reservation cycle, and a reservation cycle ends when every busy user has successfully placed a reservation for a data slot. To accommodate prioritized reservation, DSMA allows the first k (k&lt;n) bits to be used to support 2.sup.k priority classes, and the remaining (n-k) bits to be used as 2.sup.(n-k) -1 distinct addresses. Each user may choose to transmit a reservation message with any one of the 2.sup.k priorities in a reservation frame by selecting appropriate bits for the first k serially transmitted bits. Since the first k bits are not unique among different users, they cannot reveal multiple users transmitting reservation messages with the same highest priority. The remaining (n-k) bits uniquely determines which user in a reservation frame has the highest priority. Note that it is guaranteed that no address is higher than one with (n-k) ones.
Some prioritized demand assignment protocols for a system consist of n stations generating messages of p different priority levels. A virtual network user is defined by a tuple (i, j) with 1.ltoreq.i.ltoreq.n and 1.ltoreq.j.ltoreq.p. One protocol for implementing message priorities is to replicate the access mechanism for each priority. For example, an n-slot scheduling frame is repeated p times, with frames assigned to different priority levels in decreasing order. Another protocol allows access rights to be passed among all virtual users of different priorities in the same station before the virtual users for the next station. For example, a p-slot scheduling frame is repeated n times, with frames assigned to different stations. In a third protocol, known as the reservation scheduling protocol (RSP), messages are transmitted following two consecutive reservation/scheduling periods: a priority reservation period followed by a station reservation period. In each reservation cycle, up to p slots are dedicated to finding the highest priority message or messages present in the system. Since multiple such messages can arrive in a given priority reservation period, a station reservation period of up to n slots is used to determine which station among the contending stations will actually have a successful reservation.
Code Division Multiple Access (CDMA) techniques allow simultaneous transmission of several messages, using coded signals with low cross-correlation, such that capture is normally possible. Each user is either permanently assigned a fixed code or can each time randomly select a code from a predetermined code book containing a set of orthogonal codes. Time Spread Multiple Access (TSMA), based on assigning unique orthogonal code words generated from a Galois field, is an example of a CDMA type protocol with a fixed code assignment per user. When permanent code assignment is used, with one distinct code per group (e.g., priority class) of users, a collision occurs in a transmission cycle when two or more users belonging to the same group transmit their messages. When random code assignment is used, a collision occurs in a transmission cycle when two or more users happen to have selected the same code from the code book. In the prior art, a splitting algorithm is used for resolving collisions due to contending users having selected the same code.
The performance of a contention resolution algorithm based on binary tree splitting is improved when there is capture. The effect of capture in a contention-based multiple access protocol is taken advantage of to support users of different priority classes. Such a phenomenon is originally due to different levels of attenuation on transmissions from different geographically distributed users. The transmission that is originated by a transmitter closest to the receiver tends to have a higher power when it arrives at the receiver site than those originated by transmitter located further away. This transmission with the highest power is likely to dominate in a collision, and thus has a higher chance of being received successfully. By allowing users to select different levels of power for their transmissions, one may support users of different priority classes.
A common existing method for implementing priority classes in multiple access protocols is to partition a channel into multiple subchannels, and replicate for each priority class a multiple access mechanism in a separate subchannel. This approach is not efficient because the overhead for dynamic reallocation of transmission resources among priority classes is inevitably high. Common methods for partitioning a channel into subchannels include orthogonal segmentation in time, frequency, and both. In the case where both time and frequency segments are allowed, orthogonal codes are assigned to users of different priority classes to specify the time-frequency segments in which users of a given priority class are allowed to transmit messages. An example of such an approach is the well known code-division multiple access (CDMA) protocol where each priority class is assigned a unique orthogonal code.
Another existing method for implementing priority classes in multiple access protocols is to use a contention-free reservation subchannel to identify the highest priority busy user in the system so that this user may access the data subchannel first. The reservation mechanism typically involves two phases. A first phase is used to determine the highest priority class with at least a busy user, and a second phase is used to uniquely identify the user that is to be first granted access privilege. The second phase may be implemented with a round-robin schedule, or a prioritized schedule. Due to the application of a contention-free reservation mechanism, the method described above is not easily scalable, and hence is inefficient when there is a large population of bursty users.
There is a need for an efficient method and system that addresses the problem of multiple access for a large population of users divided among a predetermined number of priority classes, each requiring a possibly different level of QoS.